|
In the area of graph theory in mathematics, a signed graph is a graph in which each edge has a positive or negative sign. Formally, a signed graph Σ is a pair (''G'', σ) that consists of a graph ''G'' = (''V'', ''E'') and a sign mapping or signature σ from ''E'' to the sign group . The graph may have loops and multiple edges as well as half-edges (with only one endpoint) and loose edges (with no endpoints). Half and loose edges do not receive signs. (In the terminology of the article on graphs, it is a ''multigraph'', but we say ''graph'' because in signed graph theory it is usually unnatural to restrict to simple graphs.) The sign of a circle (this is the edge set of a simple cycle) is defined to be the product of the signs of its edges; in other words, a circle is positive if it contains an even number of negative edges and negative if it contains an odd number of negative edges. The fundamental fact about a signed graph is the set of positive circles, denoted by ''B''(Σ). A signed graph, or a subgraph or edge set, is called balanced if every circle in it is positive (and it contains no half-edges). Two fundamental questions about a signed graph are: Is it balanced? What is the largest size of a balanced edge set in it? The first question is not difficult; the second is computationally intractable (technically, it is NP-hard). Signed graphs were first introduced by Harary to handle a problem in social psychology (Cartwright and Harary, 1956). They have been rediscovered many times because they come up naturally in many unrelated areas. For instance, they enable one to describe and analyze the geometry of subsets of the classical root systems. They appear in topological graph theory and group theory. They are a natural context for questions about odd and even cycles in graphs. They appear in computing the ground state energy in the non-ferromagnetic Ising model; for this one needs to find a largest balanced edge set in Σ. They have been applied to data classification in correlation clustering. ==Examples== * The complete signed graph on ''n'' vertices with loops, denoted by ±''K''''n''o, has every possible positive and negative edge including negative loops, but no positive loops. Its edges correspond to the roots of the root system ''C''''n''; the column of an edge in the incidence matrix (see below) is the vector representing the root. * The complete signed graph with half-edges, ±''K''''n''', is ±''K''''n'' with a half-edge at every vertex. Its edges correspond to the roots of the root system ''B''''n'', half-edges corresponding to the unit basis vectors. * The complete signed link graph, ±''K''''n'', is the same but without loops. Its edges correspond to the roots of the root system ''D''''n''. * An all-positive signed graph has only positive edges. If the underlying graph is ''G'', the all-positive signing is written +''G''. * An all-negative signed graph has only negative edges. It is balanced if and only if it is bipartite because a circle is positive if and only if it has even length. An all-negative graph with underlying graph ''G'' is written −''G''. * A signed complete graph has as underlying graph ''G'' the ordinary complete graph ''K''''n''. It may have any signs. Signed complete graphs are equivalent to two-graphs, which are of value in finite group theory. A two-graph can be defined as the class of vertex sets of negative triangles (having an odd number of negative edges) in a signed complete graph. 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「signed graph」の詳細全文を読む スポンサード リンク
|